import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25228
 * Date: 2024-10-05
 * Time: 8:42
 */
//https://leetcode.cn/problems/top-k-frequent-words/
//前k个高频词
class Solution2 {
    public List<String> topKFrequent(String[] words, int k) {
        //哈希计算频率
        HashMap<String,Integer> map=new HashMap<>();
        for (int i = 0; i <words.length ; i++) {
            map.put(words[i],map.getOrDefault(words[i],0)+1);
        }

        //利用小根堆将频率高的放至堆顶
        PriorityQueue<String> queue=new PriorityQueue<>(new Comparator<String>(){
            @Override
            public int compare(String s1, String s2){
                int frs=Integer.compare(map.get(s1),map.get(s2));
                if(frs!=0){
                    return frs;
                }else{
                    return s2.compareTo(s1);
                }
            }
        });
        //将数据放入堆中
        for (String s:map.keySet()) {
            queue.offer(s);
            if(queue.size()>k){
                queue.poll();
            }
        }
        //将数据从堆中取到链表里
        List<String> list=new ArrayList<>(k);
        while (!queue.isEmpty()){
            list.add(queue.poll());
        }
        Collections.reverse(list);
        return list;
    }
}
